package org.example.myleet.rosalind.ctea;

import org.example.myleet.rosalind.utils.FastaReader;
import org.example.myleet.rosalind.utils.FastaSequence;

import java.util.List;

public class Solution {

    private static final int MOD_BASE = 134217727;

    public static void main(String[] args) {
        Solution solution = new Solution();
        String path = solution.getClass().getResource("").getPath();
        path += "example.txt";
        List<FastaSequence> sequences = FastaReader.parseFastaFromFile(path);
        //construct edit distance status matrix
        String s = sequences.get(0).getSequence();
        String t = sequences.get(1).getSequence();
        int m = s.length(), n = t.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; ++i) {
            //和空字符串都不匹配，编辑距离等于字符串长度
            dp[i][0] = i;
        }
        for (int j = 1; j <= n; ++j) {
            //和空字符串都不匹配，编辑距离等于字符串长度
            dp[0][j] = j;
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    //字符匹配，则无需增加编辑距离
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    //不匹配，则有3种选择
                    //1. 选用dp[i-1][j-1]+1，即s[i-1]和t[j-1]不匹配但通过替换从s变成t上面对应的字符
                    //2. 选用dp[i][j-1]+1，即s[i-1]和t[j-1]不匹配但通过选用s[i]插入、t字符串跳过一个字符匹配（使用"-"表示）
                    //3. 选用dp[i-1][j]+1，即s[i-1]和t[j-1]不匹配但通过选用t[j]插入、s字符串跳过一个字符匹配（使用"-"表示）
                    //从中选一种编辑距离最小的得到dp[i][j]
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
                }
            }
        }
        //然后从dp[m][n]位置通过回溯找到可能的alignment数量
        long[][] memo = new long[m + 1][n + 1];
        long count = dfs(dp, memo, s, t, m, n);
        System.out.println(count);
    }

    private static long dfs(int[][] matrix, long[][] memo, String s, String t, int m, int n) {
        if (0 == m || 0 == n) {
            //搜索到末端，记忆化
            memo[m][n] = 1L;
            return 1L;
        }
        long totalCount = 0L;
        if (matrix[m][n] == matrix[m - 1][n] + 1) {
            //此状态可以从s少一个字符的方式推导过来，则增加这一条路径的搜索
            if (memo[m - 1][n] > 0) {
                totalCount += memo[m - 1][n];
            } else {
                totalCount += dfs(matrix, memo, s, t, m - 1, n);
            }
            totalCount %= MOD_BASE;
        }
        if (matrix[m][n] == matrix[m][n - 1] + 1) {
            //此状态可以从t少一个字符的方式推导过来，则增加这一条路径的搜索
            if (memo[m][n - 1] > 0) {
                totalCount += memo[m][n - 1];
            } else {
                totalCount += dfs(matrix, memo, s, t, m, n - 1);
            }
            totalCount %= MOD_BASE;
        }
        if (matrix[m][n] == matrix[m - 1][n - 1] + 1 || (matrix[m][n] == matrix[m - 1][n - 1] && s.charAt(m - 1) == t.charAt(n - 1))) {
            //此状态可以从替换一个字符的方式推导过来，或者s和t在此位置上的字符是匹配的，则增加这一条路径的搜索
            if (memo[m - 1][n - 1] > 0) {
                totalCount += memo[m - 1][n - 1];
            } else {
                totalCount += dfs(matrix, memo, s, t, m - 1, n - 1);
            }
            totalCount %= MOD_BASE;
        }
        //此节点下面的子节点都搜索完毕，记忆化
        memo[m][n] = totalCount;
        return totalCount;
    }
}
